﻿#include <iostream>
#include <string>
using namespace std;


// [编程题]游游的重组偶数
//https://www.nowcoder.com/questionTerminal/d1ac7f15d5dc40b39a7d6cb11a01407e


//int main()
//{
//    int q;
//    cin >> q;
//
//    while (q--)
//    {
//        string s;
//        cin >> s;
//        int n = s.size();
//        for (int i = n - 1; i >= 0; i--)
//        {
//            if ((s[i] - '0') % 2 == 0)
//            {
//                swap(s[i], s[n - 1]);
//                break;
//            }
//        }
//        if ((s[n - 1] - 0) % 2 == 0)
//            cout << s << endl;
//        else
//            cout << -1 << endl;
//    }
//}


//体操队形（DFS + 枚举）
//https://ac.nowcoder.com/acm/problem/229386


//int n;
//bool vis[11];
//int arr[11];
//int cnt = 0;
//
//void dfs(int floor)
//{
//	if (floor == n + 1)
//	{
//		cnt++;
//		return;
//	}
//
//	for (int i = 1; i <= n; i++)
//	{
//		if (vis[i])//当前队员放过了 - 这个位置的方案不行，剪枝
//			continue;
//		if (vis[arr[i]])//需求队员已经在前面了 - 上个位置的方案已经不行了，剪大枝
//			return;
//
//		vis[i] = 1;//相当于当前位置放上i队员
//		dfs(floor + 1);
//		vis[i] = 0;
//	}
//}
//
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++) cin >> arr[i];
//
//	dfs(1);
//
//	cout << cnt << endl;
//}

// ⼆叉树中的最⼤路径和（树形dp）
//https://www.nowcoder.com/practice/da785ea0f64b442488c125b441a4ba4a?tpId=196&tqId=37050&ru=/exam/oj


//struct TreeNode {
//    int val;
//    TreeNode* left;
//    TreeNode* right;
//    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//};
 
//每层递归目标：经过当前根节点的最大“路径和”
//需要子树提供：经过子树根节点的最大“单链和”
//每层递归返回：经过当前根节点的最大“单链和”

//class Solution {
//public:
//    int dfs(TreeNode* root) {
//        if (root == nullptr) return 0;
//
//        int l = max(0, dfs(root->left));    //左子树最大“单链和”
//        int r = max(0, dfs(root->right));   //右子树最大“单链和”
//
//        ret = max(root->val + l + r, ret);  //经过当前根节点的最大“路径和”
//
//        return root->val + max(l, r);       //经过当前根节点的最大“单链和”
//    }
//
//    int maxPathSum(TreeNode* root) {
//        ret = root->val;
//        dfs(root);
//        return ret;
//    }
//
//    int ret;
//};